class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # s横，p纵
        # 土味拼音变量名
        # '?' 可以匹配任何单个字符。
        # '*' 可以匹配任意字符串（包括空字符串）。也就是说.不能消除前面一个！！！！
        zong = len(p) + 1  # 纵轴长度
        heng = len(s) + 1  # 横轴长度

        table = [[False] * heng for i in range(zong)]
        table[0][0] = True

        if p.startswith("*"):
            table[1] = [True] * heng

        for m in range(1, zong):
            path = False  # 是否可以在该行使用*的特技
            for n in range(1, heng):
                if p[m - 1] == "*":  # m是表格的索引，但不是p的索引
                    if table[m - 1][0] == True:
                        table[m] = [True] * heng
                    if table[m - 1][n]:  # 只要顶上有了True，就可以开通*接下来的所有道路
                        path = True
                    if path:
                        table[m][n] = True
                elif p[m - 1] == "?" or p[m - 1] == s[n - 1]:  # 先判断字母是否符合
                    table[m][n] = table[m - 1][n - 1]  # 再看左上方格子是不是T

        return table[zong - 1][heng - 1]

'''
动态规划
// 初始化：
//      1. dp[0][0] 表示什么都没有，其值为 true
//      2. 第一行 dp[0][j]，换句话说，s 为空，与 p 匹配，所以只要 p 开始为 * 才为 true
//      3. 第一列 dp[i][0]，当然全部为 false
从1开始因为0哪行用了!

'''


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s) + 1 , len(p) + 1

        dp = [[False] * n for _ in range(m)]
        dp[0][0] = True
        for j in range(1, n):
            if p[j - 1] == '*':
                dp[0][j] = True
            else:
                break

        for i in range(1, m):
            for j in range(1, n):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m-1][n-1]



















